churchsche Hypothese


churchsche Hypothese
I
churchsche Hypothese,
 
Turing-Maschine.
II
churchsche Hypothese
 
['tʃəːtʃ-], die von A. Church 1936 aufgestellte Annahme, dass jede berechenbare Funktion rekursiv sei. Die churchsche Hypothese versucht die intuitive Berechenbarkeit als Rekursivität zu präzisieren und ist implizit auch in A. M. Turings Begriff einer allgemeinen Rechenmaschine enthalten (Turing-Maschine). In der mathematischen Praxis wird die churchsche Hypothese gegenwärtig akzeptiert, da für ihre Plausibilität v. a. spricht, dass sich bisher alle anderen, von zum Teil stark abweichenden Ausgangspunkten her unternommenen Präzisierungsversuche des Berechenbarkeitsbegriffs als gleichwertig erwiesen haben.

Universal-Lexikon. 2012.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Church — I Church,   Turing Maschine. II Church   [tʃəːtʃ],    1) Alonzo, amerikanischer Mathematiker und Logiker, * Washington (D. C.) 14. 6. 1903, ✝ Hudson (Ohio) 11. 8. 1995; seit 1939 Professor an der Pr …   Universal-Lexikon

  • rekursive Funktion — rekursive Funktion,   in der Mathematik eine mittels rekursiver Definition gewonnene Funktion, für die es ein Berechnungsverfahren der Funktionswerte gibt. Als primitiv rekursiv (K. Gödel, 1931) bezeichnet man:   a) die Zahl 0; die Funktion f (x1 …   Universal-Lexikon

  • Turing-Maschine — Tu|ring|ma|schi|ne auch: Tu|ring Ma|schi|ne 〈[tju: ] f. 19〉 theoretisches Modell einer Rechenmaschine mit unendlich großem Speicher, in dem sich diese von ihrer momentanen Position nur um eine Position vor od. zurück bewegen kann [nach dem engl.… …   Universal-Lexikon

  • berechenbare Funktion — I berechenbare Funktion,   Informatik, mathematische Logik: eine Funktion f : M → N, für die es einen Algorithmus gibt, der für jeden Eingabewert …   Universal-Lexikon